class NumMatrix(object):

    def __init__(self, matrix):
        """
        :type matrix: List[List[int]]
        """
        self.prefix = matrix
        m = len(matrix)
        n = len(matrix[0])
        for i in range(1, m):
            self.prefix[i][0] += self.prefix[i - 1][0]
        for j in range(1, n):
            self.prefix[0][j] += self.prefix[0][j - 1]
        for i in range(1, m):
            for j in range(1, n):
                self.prefix[i][j] = self.prefix[i][j - 1] + self.prefix[i - 1][j] - self.prefix[i - 1][j - 1] + \
                                    self.prefix[i][j]

    def sumRegion(self, row1, col1, row2, col2):
        """
        :type row1: int
        :type col1: int
        :type row2: int
        :type col2: int
        :rtype: int
        """
        if row1 == 0:
            if col1 == 0:
                return self.prefix[row2][col2]
            else:
                return self.prefix[row2][col2] - self.prefix[row2][col1 - 1]
        else:
            if col1 == 0:
                return self.prefixp[row2][col2] - self.prefix[row1 - 1][col2]
            else:
                return self.prefix[row2][col2] - self.prefix[row1 - 1][col2] - self.prefix[row2][col1 - 1] + \
                       self.prefix[row1 - 1][col1 - 1]
